
//二叉树的镜像
class Solution {
public:
    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot == nullptr)
            return nullptr;

        TreeNode* tmp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = tmp;

        Mirror(pRoot->left);
        Mirror(pRoot->right);

        return pRoot;
    }
};


//判断是不是搜索二叉树
class Solution {
public:
    bool _isValidBST(TreeNode* cur,int& prev)
    {
        if(cur == nullptr)
            return true;

        if(!_isValidBST(cur->left,prev))
            return false;

        if(cur->val <= prev)
            return false;
        prev = cur->val;

        if(!_isValidBST(cur->right,prev))
            return false;
        return true;
    } 


    bool isValidBST(TreeNode* root) {
        int prev = INT_MIN;
        return _isValidBST(root ,prev);
    }
};


//判断是不是完全二叉树
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        TreeNode* cur = root;
        q.push(root);
        while(q.front())
        {
            TreeNode* front = q.front();
            q.pop();
            q.push(front->left);
            q.push(front->right);
        }
        
        while(!q.empty())
        {
            if(q.front())
                return false;
            q.pop();
        }
        return true;
    }
};

//判断是不是平衡二叉树
class Solution {
public:
    int Height(TreeNode* root)
    {
        if(root == nullptr)
            return 0;
        int left = Height(root->left);
        int right = Height(root->right);
        return max(left,right) + 1;
    }

    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot == nullptr)
            return true;

        int left = Height(pRoot->left);
        int right = Height(pRoot->right);
        if(abs(left - right) > 1)
            return false;

        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
};

//二叉搜索树的最近公共祖先
class Solution {
public:
    void GetPath(TreeNode* root,int x,stack<int>& s)
    {
        s.push(root->val);
        if(root->val == x)
            return;
        if(root->val > x)
            GetPath(root->left, x, s);
        else
            GetPath(root->right,x,s);

    }

    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        stack<int> sp;
        stack<int> sq;
        GetPath(root,p,sp);
        GetPath(root,q,sq);

        int psize = sp.size();
        int qsize = sq.size();

        while(sp.top() != sq.top())
        {
            if(psize > qsize)
            {
                sp.pop();
                --psize;
            }
            else if(psize < qsize)
            {
                sq.pop();
                --qsize;
            }
            else {
                sq.pop();
                sp.pop();
                --qsize;
                --psize;
            }
        }
        return sp.top();
    }
};
